#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sys/time.h>

using namespace std;
static int cmptimes=0;

/*
选择排序
　　选择排序是这样实现的：
　　设数组内存放了n个待排数字，数组下标从1开始，到n结束。
　　i=1
　　从数组的第i个元素开始到第n个元素，寻找最小的元素。
　　将上一步找到的最小元素和第i位元素交换。
　　如果i=n－1算法结束，否则回到第3步
　　选择排序的平均时间复杂度是O(n^2;)的。
*/
template<typename sortelement>
bool chooseSort(sortelement* listhead, const unsigned int listsize, bool asc=true)
{
	if(NULL == listhead)
	{
		return false;
	}

	if(listsize<2)
	{
		return true;
	}
	for(unsigned int i=0; i<listsize-1; ++i)
	{
		for(unsigned int j=i+1; j<listsize; ++j)
		{
			if(asc)
			{
				if(listhead[i]>listhead[j])
				{
					sortelement tmp = listhead[i];
					listhead[i] = listhead[j];
					listhead[j] = tmp;
				}
			}
			else
			{
				if(listhead[i]<listhead[j])
				{
					sortelement tmp = listhead[i];
					listhead[i] = listhead[j];
					listhead[j] = tmp;
				}
			}
		}
	}
	return true;
}

/*
冒泡排序()
　　冒泡排序是这样实现的：
　　首先将所有待排序的数字放入工作列表中。
　　从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。
　　重复2号步骤，直至再也不能交换。
　　冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法
*/
template<typename sortelement>
bool bubbleSort(sortelement* listhead, const unsigned int listsize, bool asc=true)
{
	if(NULL == listhead)
	{
		return false;
	}

	if(listsize<2)
	{
		return true;
	}
	for(unsigned int i=0; i<listsize-1; ++i)
	{
		for(unsigned int j=0; j<listsize-1-i; ++j)
		{
			if(asc)
			{
				if(listhead[j]>listhead[j+1])
				{
					sortelement tmp = listhead[j];
					listhead[j] = listhead[j+1];
					listhead[j+1] = tmp;
				}
			}
			else
			{
				if(listhead[j]<listhead[j+1])
				{
					sortelement tmp = listhead[j];
					listhead[j] = listhead[j+1];
					listhead[j+1] = tmp;
				}
			}
		}
	}
	return true;
}

/*
快速排序(Quicksort)
	通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
	然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

	下面的quickSort方法，asc=true实现前小后大的排序，
*/
template<typename sortelement>
bool quickSort(sortelement* listhead, const unsigned int listsize, bool asc=true)
{
	if(NULL == listhead)
	{
		return false;
	}

	if(listsize<2)
	{
		return true;
	}
	if(listsize == 2)
	{
		if(asc)
		{
			if(listhead[1] < listhead[0])
			{
				sortelement tmp = listhead[0];
				listhead[0] = listhead[1];
				listhead[1] = tmp;
			}
		}
		else
		{	
			if(listhead[1] > listhead[0])
			{
				sortelement tmp = listhead[0];
				listhead[0] = listhead[1];
				listhead[1] = tmp;
			}
		}
		return true;
	}

	sortelement key=listhead[0];
	unsigned int headpos = 0;
	unsigned int tailpos = listsize-1;

	while(true)
	{
		while(tailpos>headpos)
		{
			if(asc)
			{
				if(listhead[tailpos] < key)
				{
					++ cmptimes;
					sortelement tmp = listhead[tailpos];
					listhead[tailpos] = listhead[headpos];
					listhead[headpos] = tmp;
					break;
				}
			}
			else
			{
				if(listhead[tailpos] > key)
				{
					++ cmptimes;
					sortelement tmp = listhead[tailpos];
					listhead[tailpos] = listhead[headpos];
					listhead[headpos] = tmp;
					break;
				}

			}
			--tailpos;
		}

		while(headpos<tailpos)
		{
			if(asc)
			{
				if(listhead[headpos] > key)
				{
					++ cmptimes;
					sortelement tmp = listhead[tailpos];
					listhead[tailpos] = listhead[headpos];
					listhead[headpos] = tmp;
					break;
				}
			}
			else
			{
				if(listhead[headpos] < key)
				{
					++ cmptimes;
					sortelement tmp = listhead[tailpos];
					listhead[tailpos] = listhead[headpos];
					listhead[headpos] = tmp;
					break;
				}
			}
			++headpos;
		}
		if(headpos == tailpos)
		{
			break;
		}
	}

	//cout<<"in quickSort, listsize="<<listsize<<"\theadpos="<<headpos<<endl;	

	if(1 < headpos)
	{
		quickSort(listhead, headpos, asc);	
	}
	if(1 < listsize-1-headpos)
	{
		sortelement* newlisthead = listhead;
		newlisthead += (headpos+1);
		quickSort(newlisthead, listsize-1-headpos, asc);
	}
	
	return true;
}

/*
堆是一种特殊完全二叉树的数组表示
	大顶堆: 长度为n的数组(1 based)A, A[i]>=a[2*i] 且 A[i]>=a[2*i+1], 
		其中i的取值从1开始，并且要使得 2*i <= n, 如此a[2*i]相当于A[i]在完全二叉树中的左子节点.
		A[i]>=a[2*i]表示节点i的值大于左子节点, A[i]>=a[2*i+1]表示节点i的值大于右子节点.
		但是这个完全二叉树不是排序二叉树，因为左子节点和右子节点的大小不是确定的
	小顶堆: 长度为n的数组(1 based)A, A[i]<=a[2*i] 且 A[i]<=a[2*i+1]

在listsize长的无序数组上通过调整元素位置，使得以apos为根形成一个大顶堆(asc=true)或是一个小顶堆
*/

// 使用栈代替递归
template<typename sortelement>
bool heapdSortAjustNoRecursion(sortelement* listhead, const unsigned int listsize, const unsigned int ajustpos, bool asc=true)
{
	if(NULL == listhead)
	{
		return false;
	}

	if(2>listsize)
	{
		return true;
	}

	//vector<unsigned int> tmpstack;
	//tmpstack.push_back(ajustpos);
	unsigned int tmpstack[1024];
	unsigned int toppos=0;
	tmpstack[toppos] = ajustpos;
	++toppos;

	sortelement tmp;
	
	unsigned int leftpos;
	unsigned int rightpos;
	unsigned int checkpos;
	unsigned int nowapos;
	while(toppos>0)
	{
		--toppos;
		nowapos = tmpstack[toppos];
		//nowapos = tmpstack.back();
		//tmpstack.pop_back();

		leftpos = 2*(nowapos+1)-1;
		rightpos = leftpos+1;
		checkpos = leftpos;

		if(leftpos>=listsize)
		{
			//左子节点超过范围
			continue;
		}
		if(rightpos < listsize)
		{
			if(asc)
			{
				if(listhead[leftpos] < listhead[rightpos])
				{
					++cmptimes;
					checkpos = rightpos;
				}
			}
			else
			{
				if(listhead[leftpos] > listhead[rightpos])
				{
					++cmptimes;
					checkpos = rightpos;
				}
			}
		}
		if(asc)
		{
			if(listhead[nowapos] < listhead[checkpos]) 
			{
				++cmptimes;
				tmp = listhead[nowapos];
				listhead[nowapos] = listhead[checkpos];
				listhead[checkpos] = tmp;

				//tmpstack.push_back(checkpos);
				tmpstack[toppos] = checkpos;
				++toppos;
				continue;
			}
		}
		else
		{
			if(listhead[nowapos] > listhead[checkpos]) 
			{
				++cmptimes;
				tmp = listhead[nowapos];
				listhead[nowapos] = listhead[checkpos];
				listhead[checkpos] = tmp;

				//tmpstack.push_back(checkpos);
				tmpstack[toppos] = checkpos;
				++toppos;
			}
		}
	}//end of while
	return true;
}

// 递归版本
template<typename sortelement>
bool heapdSortAjust(sortelement* listhead, const unsigned int listsize, const unsigned int ajustpos, bool asc=true)
{
	//return heapdSortAjustNoRecursion(listhead, listsize, ajustpos, asc);

	if(NULL == listhead)
	{
		return false;
	}

	if(2>listsize)
	{
		return true;
	}

	unsigned int nowapos = ajustpos;
	unsigned int leftpos = 2*(nowapos+1)-1;
	unsigned int rightpos = leftpos+1;
	unsigned int checkpos = leftpos;
	if(leftpos>=listsize)
	{
		//左子节点超过范围
		return true;
	}
	if(rightpos < listsize)
	{
		if(asc)
		{
			if(listhead[leftpos] < listhead[rightpos])
			{	
				++cmptimes;
				checkpos = rightpos;
			}
		}
		else
		{
			if(listhead[leftpos] > listhead[rightpos])
			{
				++cmptimes;
				checkpos = rightpos;
			}
		}
	}

	if(asc)
	{
		if(listhead[nowapos] < listhead[checkpos]) 
		{
			++cmptimes;
			sortelement tmp = listhead[nowapos];
			listhead[nowapos] = listhead[checkpos];
			listhead[checkpos] = tmp;

			heapdSortAjust(listhead, listsize, checkpos, asc);
		}
	}
	else
	{
		if(listhead[nowapos] > listhead[checkpos]) 
		{
			++cmptimes;
			sortelement tmp = listhead[nowapos];
			listhead[nowapos] = listhead[checkpos];
			listhead[checkpos] = tmp;

			heapdSortAjust(listhead, listsize, checkpos, asc);
		}
	}
	return true;
}


template<typename sortelement>
bool heapSort(sortelement* listhead, const unsigned int listsize, bool asc=true)
{
	if(NULL == listhead)
	{
		return false;
	}
	// 无序数组调整成大顶堆(asc==true),或是小顶堆
	// 做法是从pos = n/2开始，调整出一个局部的堆，然后减小pos，直到数组的第一个元素也调整好，
	// 这样整个数组就变成堆了，虽然还是无序的，但是堆顶一定已经是最大的(asc==true)或是最小的了
	for(unsigned int ajustpos = listsize/2; ajustpos>0; --ajustpos)
	{
		heapdSortAjust(listhead, listsize, ajustpos, asc);
	}
	heapdSortAjust(listhead, listsize, 0, asc);

	sortelement tmp;
	for(unsigned int loop=0; loop<listsize-1; ++loop)
	{
		// 顶堆 和 无序部分的末尾元素交换,如此末尾元素直到整个数组的结尾部分就是有序的了
		unsigned int swappos = listsize-1-loop;

		tmp = listhead[swappos];
		listhead[swappos] = listhead[0];
		listhead[0] = tmp;

		// 数组首元素因为是交换过来的，因此可能在size为 listsize-1-loop 条件下不满足堆的条件，调整之
		heapdSortAjust(listhead, listsize-1-loop, 0, asc);
	}
	return true;
}


template<typename sortelement>
bool showList(sortelement* listhead, const unsigned int listsize, bool asc=true, int showsize=0)
{
	if(NULL == listhead)
	{
		return false;
	}

	if(showsize<0)
	{
		return true;
	}
	if(asc)
	{
		unsigned int showlen = (0==showsize ? listsize : ((unsigned int)showsize>listsize ? listsize : (unsigned int)showsize) );
		for(unsigned int i=0; i< showlen; ++i)
		{
			cout<<i<<" -> "<<listhead[i]<<endl;
		}
	}
	else
	{
		unsigned int showlen = (0==showsize ? listsize : ((unsigned int)showsize>listsize ? listsize : (unsigned int)showsize) );
		for(int i = (int)(showlen-1); i >= 0; --i)
		{
			cout<<i<<" -> "<<listhead[i]<<endl;
		}
	}
	return true;
}

int main()
{
	timeval clkEnd, clkBegin;
	long timecostusec,timecostms;

	unsigned int inputsize = 30000;
	const unsigned int showsize = 10;
	bool sasc=false;
//*
	// ========== try to test chooseSort
	cmptimes=0;
	int* testintlist = new int[inputsize];
	gettimeofday(&clkBegin, NULL);
	//srand(int(clkBegin.tv_usec));
	srand(0);
	for(unsigned int loop=0;loop<inputsize;++loop)
	{
		testintlist[loop] = (int)rand();
	}
	gettimeofday(&clkBegin, NULL);
	chooseSort<int>(testintlist, inputsize, sasc);
	gettimeofday(&clkEnd, NULL);
	timecostusec = (clkEnd.tv_usec - clkBegin.tv_usec);
	timecostusec += 1000000L*(clkEnd.tv_sec - clkBegin.tv_sec);
	timecostms = timecostusec/1000L;
	cout<<"choose sort time: "<<timecostusec<<" us = "<<timecostms<<" ms"<<endl;

	showList<int>(testintlist, inputsize, true, showsize);

	// ========== try to test bubbleSort 
	cmptimes=0;
	long* testlonglist = new long[inputsize];
	//srand(int(clkBegin.tv_usec));
	srand(0);
	for(unsigned int loop=0;loop<inputsize;++loop)
	{
		testlonglist[loop] = (long)rand();
	}
	gettimeofday(&clkBegin, NULL);
	bubbleSort<long>(testlonglist, inputsize, sasc);
	gettimeofday(&clkEnd, NULL);
	timecostusec = (clkEnd.tv_usec - clkBegin.tv_usec);
	timecostusec += 1000000L*(clkEnd.tv_sec - clkBegin.tv_sec);
	timecostms = timecostusec/1000L;
	cout<<"bubble sort time: "<<timecostusec<<" us = "<<timecostms<<" ms"<<endl;

	showList<long>(testlonglist, inputsize, true, showsize);
//*/

	// ========== try to test quickSort 
	cmptimes=0;
	double* testdoublelist = new double[inputsize];
	//srand(int(clkBegin.tv_usec));
	srand(0);
	for(unsigned int loop=0;loop<inputsize;++loop)
	{
		//break;
		testdoublelist[loop] = (double)rand();
	}
	gettimeofday(&clkBegin, NULL);
	quickSort<double>(testdoublelist, inputsize, sasc);
	gettimeofday(&clkEnd, NULL);
	timecostusec = (clkEnd.tv_usec - clkBegin.tv_usec);
	timecostusec += 1000000L*(clkEnd.tv_sec - clkBegin.tv_sec);
	timecostms = timecostusec/1000L;
	cout<<"quick sort time: "<<timecostusec<<" us = "<<timecostms<<" ms"<<endl;
	cout<<"quickSort cmptimes="<<cmptimes<<endl;

	showList<double>(testdoublelist, inputsize, true, showsize);

	// ========== try to test heapSort 
	cmptimes=0;
	srand(0);
	float* testfloatlist = new float[inputsize];
	for(unsigned int loop=0;loop<inputsize;++loop)
	{
		//break;
		testfloatlist[loop] = (float)rand();
	}
	gettimeofday(&clkBegin, NULL);
	heapSort<float>(testfloatlist, inputsize, sasc);
	gettimeofday(&clkEnd, NULL);
	timecostusec = (clkEnd.tv_usec - clkBegin.tv_usec);
	timecostusec += 1000000L*(clkEnd.tv_sec - clkBegin.tv_sec);
	timecostms = timecostusec/1000L;
	cout<<"heap sort time: "<<timecostusec<<" us = "<<timecostms<<" ms"<<endl;
	cout<<"heapSort, cmptimes="<<cmptimes<<endl;

	showList<float>(testfloatlist, inputsize, true, showsize);

	// ========== try to test std vector sort 
	cmptimes=0;
	srand(0);
	vector<float> tmpfloatlist;
	for(unsigned int loop=0;loop<inputsize;++loop)
	{
		tmpfloatlist.push_back((float)rand());
	}
	gettimeofday(&clkBegin, NULL);
	sort(tmpfloatlist.begin(), tmpfloatlist.end());
	gettimeofday(&clkEnd, NULL);
	timecostusec = (clkEnd.tv_usec - clkBegin.tv_usec);
	timecostusec += 1000000L*(clkEnd.tv_sec - clkBegin.tv_sec);
	timecostms = timecostusec/1000L;
	cout<<"std vector sort time: "<<timecostusec<<" us = "<<timecostms<<" ms"<<endl;

	for(unsigned int loop=0; loop<showsize; ++loop)
	{
		cout<<loop<<" --> "<<tmpfloatlist[loop]<<endl;
	}
	return 0;
}
